1 Contenido de la clase
Trabajo sobre el grafo: vértices, grados y adyacencia [02:30-10:00]
La clase comienza sobre un grafo dibujado en la pizarra, con vértices numerados. El profesor pregunta "¿qué lado tiene el 8?" [02:37] y se van revisando los grados de los vértices [02:39-03:31]. Se busca identificar el vértice de menor grado: "te pregunto: en el de menor grado, ¿cuál sería este vértice de menor grado?" [07:24-07:43], y se menciona "voy a sacar el más grande" [04:09]. En un momento se propone "ordenar por peso" [08:07-08:09] y se discute qué vértices "no se tocan", es decir, no son adyacentes ("B6 no se tocan más", "A B8, sí" [09:58-10:00]). [parte no entendida: los números concretos del ejemplo y el detalle del recorrido se pierden por el ruido de la grabación.]
La representación por listas [27:14-27:39]
El profesor comenta que el grafo se puede representar como "una lista de N listas, expresadas en pares": cada vértice (Vértice 1, Vértice 2, …) tiene su propia lista [27:18-27:24]. Esa es la representación habitual por listas de adyacencia. La forma de recorrer la estructura es "bajar del inicio al final" y comparar los grados de los vértices [27:35-28:11].
La triangulación: caras, aristas interiores y la frontera [21:07-26:40, 47:06-47:35]
Aparece el tema central: triangular un polígono. Se plantea la pregunta de cuántas caras hay: "¿contamos el número de caras?" [26:30-26:37]. Se distingue entre las aristas interiores —las diagonales que interesan ("tenemos que tener una lista de aristas interiores, que son las que nos interesan" [47:06-47:09])— y la frontera del polígono, que "no nos interesa que esté afuera" [47:10-47:23]. El resultado clásico que responde a esas preguntas: una triangulación de un polígono de n vértices tiene n−2 triángulos (caras) y n−3 aristas interiores (diagonales). [parte no entendida: la demostración en la pizarra.]
¿Cuántas triangulaciones hay? Los números de Catalan [21:16-21:30]
La pregunta clave de la clase es de conteo: "imagínate que hay que usar esto. ¿Cuántas combinaciones de triangulación?" [21:16-21:20]. La respuesta es el (n−2)-ésimo número de Catalan: 1, 1, 2, 5, 14, 42, 132, … para polígonos de 3, 4, 5, 6, 7, 8, 9 vértices. Los números de Catalan cumplen la recurrencia
Cₙ = C₀·Cₙ₋₁ + C₁·Cₙ₋₂ + … + Cₙ₋₁·C₀
que es la misma recurrencia que cuenta los árboles binarios (existe una biyección entre triangulaciones de un polígono y árboles binarios). [parte no entendida: el desarrollo completo de la recurrencia en la pizarra.]
Grados de los vértices y rotaciones [25:32-26:40, 28:52-29:10, 40:00-40:24]
Se discute el número de giros o rotaciones: "el número de giros que uno tiene que hacer" [25:32]; "¿cuántos giros hay?" [25:57, 26:18]. Una rotación (flip) consiste en quitar una diagonal y reemplazarla por la otra diagonal del cuadrilátero que forman sus cuatro vértices, de modo que se obtiene otra triangulación válida: "ya podemos tener un control de cuáles son las rotaciones" [47:13-47:15]; "¿podré yo girar?" [40:14]. [parte no entendida en el detalle de las rotaciones y sus conteos.]
Cierre: comprobaciones con los ángulos [62:31-63:38]
El tramo final es casi inaudible. Se alcanza a percibir una discusión sobre valores ("tenemos 4, lo confirmamos, y luego tenemos 1" [62:45]) y sobre ángulos: "el ángulo de uno y de tres y nueve es mayor a… menor a…" [63:04-63:07], probablemente comprobando condiciones de validez de un triángulo o de una diagonal. [parte no entendida — tramo final 62:31-63:38.]
2 Puntos destacados / Lo que hay que saber
3 Actividades y tareas pendientes
En esta clase no se dejó ninguna tarea concreta con fecha de entrega. Conviene practicar por cuenta propia:
4 Dudas que podrían examinar
¿Qué es una triangulación de un polígono?
Una partición del polígono en triángulos usando diagonales que no se cruzan, con los vértices del propio polígono [21:16-21:30].
¿Cuántos triángulos tiene una triangulación de un polígono de n vértices?
n−2 triángulos.
¿Cuántas aristas interiores (diagonales) usa?
n−3 diagonales (aristas interiores), además de los n lados de la frontera.
¿Cuántas triangulaciones distintas tiene un polígono de n lados?
El (n−2)-ésimo número de Catalan: 2 para un cuadrado, 5 para un pentágono, 14 para un hexágono [21:16-21:30].
¿Qué relación tienen los números de Catalan con los árboles binarios?
Comparten la misma recurrencia Cₙ = Σ Cₖ·Cₙ₋₁₋ₖ y existe una biyección entre triangulaciones de un polígono y árboles binarios.
¿Qué es una rotación (flip) en una triangulación?
Quitar una diagonal y poner la otra diagonal del cuadrilátero que forman sus cuatro vértices; produce otra triangulación válida [47:13-47:15].
5 Sitios o recursos para visitar
El profesor no citó libros, páginas ni herramientas concretas en esta clase. Recursos útiles para profundizar lo explicado:
Número de triangulaciones de un polígono y números de Catalan. · wikipedia.org
Definición, recurrencia y aplicaciones (triangulaciones, árboles binarios, paréntesis). · wikipedia.org
Teorema de las dos orejas: todo polígono simple tiene al menos dos "orejas" (vértices de grado 2). · wikipedia.org
Demostración del teorema de las dos orejas y del conteo n−2 / n−3. · cut-the-knot.org
Recurrencia, programación dinámica y números de Catalan para contar triangulaciones. · glc.us.es
Búsqueda general para profundizar el tema. · google.com
6 Glosario de términos
- Triangulación de un polígono: partición del polígono en triángulos mediante diagonales que no se cruzan.
- Vértice / arista: los puntos y segmentos del polígono visto como grafo.
- Grado de un vértice: número de aristas que inciden en el vértice.
- Vértice de menor grado: el vértice con menos aristas; en una triangulación siempre hay vértices de grado pequeño (de grado 2, llamados "orejas").
- Oreja (ear): triángulo formado por tres vértices consecutivos del polígono; equivale a un vértice de grado 2.
- Diagonal / arista interior: segmento entre dos vértices no consecutivos; en una triangulación hay n−3.
- Cara / triángulo: cada región triangular de la triangulación; hay n−2.
- Listas de adyacencia: representación del grafo como "una lista de N listas", una por vértice, con sus vecinos.
- Número de Catalan: sucesión 1, 1, 2, 5, 14, 42, 132, … ; el (n−2)-ésimo cuenta las triangulaciones de un polígono de n lados.
- Rotación (flip): operación que cambia una diagonal por la otra del cuadrilátero y produce otra triangulación.
7 Mapa mental textual
- Diseño Y Análisis De Algoritmos · Clase 8
- Triangulaciones de polígonos
- El polígono como grafo: vértices y grados
- Vértice de menor grado [07:24]
- "Ordenar por peso"; vértices que "no se tocan" (adyacencia)
- Representación por listas
- "Una lista de N listas" (listas de adyacencia) [27:18]
- Partes de una triangulación
- Caras (triángulos): n−2
- Aristas interiores (diagonales): n−3
- Frontera del polígono (no interesa)
- Conteo de triangulaciones
- "¿Cuántas combinaciones de triangulación?" [21:16]
- (n−2)-ésimo número de Catalan: 1, 1, 2, 5, 14, 42, …
- Recurrencia Cₙ = Σ Cₖ·Cₙ₋₁₋ₖ
- Misma recurrencia que los árboles binarios
- Rotaciones (flips) entre triangulaciones
- Quitar una diagonal y poner la otra del cuadrilátero
- "Control de cuáles son las rotaciones" [47:13]
- Comprobaciones con ángulos
- Cierre, en su mayoría inaudible [62:31-63:38]
- Triangulaciones de polígonos